package com.zyk.leetcode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author zhangsan
 * @date 2021/4/22 15:03
 */
public class M0813 {

    // 暴力尝试
    public static int pileBox(int[][] box) {
        Arrays.sort(box, (a, b) -> a[0] == b[0] ? a[1] == b[1] ? b[2] - a[2] : b[1] - a[1] : a[0] - b[0]);
        return process(box, -1, 0);
    }

    public static int process(int[][] box, int pre, int cur) {
        if (cur == box.length) return 0;
        int p1 = 0;
        if (pre == -1 || (box[cur][0] > box[pre][0] && box[cur][1] > box[pre][1] && box[cur][2] > box[pre][2])) {
            p1 = process(box, cur, cur + 1) + box[cur][2];
        }
        int p2 = process(box, pre, cur + 1);
        return Math.max(p1, p2);
    }

    // 傻缓存
    public static int pileBox2(int[][] box) {
        Arrays.sort(box, (a, b) -> a[0] == b[0] ? a[1] == b[1] ? b[2] - a[2] : b[1] - a[1] : a[0] - b[0]);
        Map<Integer, Map<Integer, Integer>> dp = new HashMap<>();
        return process(box, -1, 0, dp);
    }

    public static int process(int[][] box, int pre, int cur, Map<Integer, Map<Integer, Integer>> dp) {
        if(dp.containsKey(pre) && dp.get(pre).containsKey(cur)) return dp.get(pre).get(cur);
        if (cur == box.length) return 0;
        int p1 = 0;
        if (pre == -1 || (box[cur][0] > box[pre][0] && box[cur][1] > box[pre][1] && box[cur][2] > box[pre][2])) {
            p1 = process(box, cur, cur + 1, dp) + box[cur][2];
        }
        int p2 = process(box, pre, cur + 1, dp);
        int ans = Math.max(p1, p2);

        if(!dp.containsKey(pre)) dp.put(pre, new HashMap<>());
        dp.get(pre).put(cur, ans);
        return ans;
    }

    // dp
    public static int pileBox3(int[][] box) {
        Arrays.sort(box, (a, b) -> a[0] == b[0] ? a[1] == b[1] ? b[2] - a[2] : b[1] - a[1] : a[0] - b[0]);
        int N = box.length;
        int[][] dp = new int[N+1][N+1];
        // pre = r,   cur = c
        // 从右往左(外层) 从下往上(内层)的过程
        for (int c = N-2; c >= 0; c--) {
            for (int r = N-1; r >= 0; r--) {

                int p1 = 0;
                if (/*r == -1 ||*/ (box[c][0] > box[r][0] && box[c][1] > box[r][1] && box[c][2] > box[r][2])) {
                    p1 = dp[c][c + 1] + box[c][2];
                }
                int p2 = dp[r][c + 1];

                dp[r][c] = Math.max(p1, p2);
            }
        }
        for (int[] nums : dp) {
            System.out.println(Arrays.toString(nums));
        }

        return dp[0][0];
    }


    public static int pileBox4(int[][] box) {
        int len = box.length;
        Arrays.sort(box, (a, b) -> a[0] == b[0] ? a[1] == b[1] ? b[2] - a[2] : b[1] - a[1] : a[0] - b[0]);
        int[] dp_val = new int[len];
        dp_val[0] = box[0][2];
        int res = dp_val[0];
        for (int i = 1; i < len; ++i) {
            int max_val = 0, base_depth = box[i][1], base_height = box[i][2];
            for (int j = 0; j < i; ++j)
                if (base_depth > box[j][1] && base_height > box[j][2])
                    max_val = Math.max(max_val, dp_val[j]);

            dp_val[i] = max_val + base_height;
            res = Math.max(res, dp_val[i]);
        }
        return res;
    }


    // for test
    public static void main(String[] args) {
//        int{}{} box = {{1, 1, 1}, {2, 2, 2}, {3, 3, 3}};
//        int{}{} box = {{1, 1, 1}, {2, 3, 4}, {2, 6, 7}, {3, 4, 5}};
        int[][] box = {{9, 9, 10}, {8, 10, 9}, {9, 8, 10}, {9, 8, 10}, {10, 8, 8}, {9, 8, 9}, {9, 8, 8}, {8, 9, 10}, {10, 9, 10}, {8, 8, 10}, {10, 9, 10}, {10, 9, 8}, {8, 9, 9}, {9, 10, 8}, {8, 9, 9}, {10, 10, 9}, {8, 9, 10}, {8, 10, 10}, {8, 9, 10}, {10, 10, 8}, {10, 10, 9}, {9, 10, 10}, {10, 8, 9}, {10, 10, 9}, {8, 9, 10}, {8, 8, 9}, {8, 10, 10}, {9, 9, 10}, {10, 8, 8}, {10, 10, 8}, {8, 9, 9}, {8, 9, 8}, {10, 10, 8}, {8, 10, 8}, {10, 9, 10}, {9, 9, 10}, {9, 9, 9}, {8, 9, 8}, {9, 8, 8}, {8, 9, 10}, {10, 10, 8}, {9, 9, 9}, {10, 10, 10}, {10, 9, 8}, {9, 8, 9}, {8, 8, 10}, {8, 8, 8}, {8, 8, 8}, {8, 9, 10}, {10, 9, 8}, {8, 10, 8}, {8, 10, 10}, {9, 10, 10}, {8, 8, 9}, {9, 9, 9}, {10, 8, 8}, {8, 10, 10}, {9, 10, 9}, {9, 9, 8}, {8, 10, 9}, {9, 8, 8}, {9, 9, 10}, {9, 10, 10}, {8, 8, 10}};
        System.out.println(pileBox(box));
        System.out.println(pileBox2(box));
        System.out.println(pileBox3(box));
        System.out.println(pileBox4(box));
    }

}
